1. Technical Field
The invention relates to computer program transformation techniques. More particularly, the invention relates to a Φ function which may be used when constructing static single assignment forms in the presence of predication.
2. Description of the Prior Art
Computer program transformation techniques include algorithms that are used to transform a sequence of instructions, such that the result of their execution is unchanged. The purpose of a series of transformations is to produce an optimized program which is either shorter in number of instructions or execution time, or that enables further transformations which may themselves produce a shorter execution time.
Many recently developed program transformation techniques are based on a program representation called static single assignment (SSA) form. An SSA form is a program representation which obeys the property that each variable (or resource) name is defined statically exactly once. A resource is a program variable. It may be a register resource such as a general purpose register, or it may be a memory location. Thus, there is a single definition which may, during program execution, be executed multiple times. For example, the single definition a=x may be executed multiple times during a program run, with different values for x during each execution.
A definition of a resource is considered to be a reaching definition at a point “P” in a program if there is a path from the definition to “P” along which the resource has not been redefined. At program locations where there are multiple reaching definitions of a variable, a special Φ function is inserted. FIGS. (1a) an (1b) are control flow graphs showing multiple reaching definitions of a variable, according to the prior art.
In FIG. 1a, a path through edge 10 on which the block 12 contains a=x joins with a path through edge 14 on which the block 16 contains a=y at join point 18. Thus, at this join point, either values “x” or “y” could be obtained for “a.” FIG. 1b is an SSA representation of the FIG. 1a control flow graph. In FIG. 1b, the block 12 containing variable a1=x is on path 10, while the block 16 containing variable a2=y is on path 14. At the join point 18, the variable a3=Φ (a1, a2). The Φ function is a notational convenience indicating that there is some function whose value is dependent upon which path is taken. This Φ function is, therefore, a non-executable instruction which expresses the confluence, at a join point in a program control flow graph, of multiple reaching definitions. Such Φ function generates a single definition of a new variable.
It is necessary to exit an SSA form to generate code that is executable by a machine (computer). In general, when an SSA form is exited, and final code generation is performed, some Φ functions may need to be materialized (i.e. copies introduced on the incoming control paths) to preserve correctness. When a form is exited to perform allocation of registers, variables a1, a2, and a3 may be merged to a single register, (see FIG. 1a). In order to correclty perform register allocation, all variables participating as operands or target of the same phi function must reside in the same register.
FIGS. 2a and 2b are control flow diagrams illustrating materialization of variables, according to the prior art. In this example, on a first path through edge 26, a1=x in block 32, and on a second path through edge 28, a2=y in block 34. At the join point 36, a3=Φ(a1, a2).
If edge 28 is taken, a2 is clearly defined. However, if edges 30 and then 26 are taken, a2 has been defined, but so has a1. If all the variables are located in the same register, then a1 has overwritten a2 and it is no longer available. In this case, the only way to preserve the correctness of the assignment to z is to materialize the variables.
FIG. 2b is a control flow diagram illustrating the materialization of the variables in FIG. 2a. After the assignment to a2,variable “t” is assigned value a2 in block 34. The value of a2 is now saved. At the point where x is assigned to a1, “t” has not been overwritten, even if variables a1, a2, and a3 have all been assigned to the same register. At the join point, “t” is used to assign to z in block 36 instead of a2. Once this transformation has been made, it is correct to assign variables a1, a2, and a3 to the same register. This is called materializing the Φ function.
A technique known as predicated execution is described in Rau, B. R., Yen, D. W. L., Yen, W., and Towle, R. A., “The Cydra 5 Departmental Super-computer, Design Philosophies, Decisions, and Trade-Offs.” IEEE Computer, January 1989, pp. 12-35; and Park, J. C. H., and Schlansker, M., “On Predicated Execution,” Hewlett-Packard Laboratories Technical Report HPL-91-58, May, 1991. A predicate is a Boolean value, such as “True” or “False.” In predicated execution, predicates are used to guard the execution of instructions. Under predicated execution, each instruction has an associated predicate which, if true, then the instruction is actually executed and which, if false, then the instruction is effectively non-operational. With the introduction of predicated execution, the confluence of definitions is no longer confined to join points in the control flow graph.
Constructing an SSA form while using predication execution presents several new challenges:                The Φ functions may occur at any point, even in branch-free code sequences.        When interferences are introduced between the Φ target and its sources, they cannot be resolved simply by placing copy instructions on the incoming edges at the join point.        Φ materialization is complicated by the fact that multiple variables related by a single phi may be live concurrently (though under different predicates).        
FIG. 3 is a control flow graph illustrating predicated execution according to the prior art. In the figure, a1 is assigned x in block 44, and a2 is assigned y in block 46. Block 38 contains the compare which determines whether block 44 or 46 is executed. Thus, if the result of the compare is “true,” block 44 is executed and if “false,” block 46 is executed. At the join point at block 48, a3=Φ(a1,a2)
When this code is transformed to predicated execution, predicates p1 and p2 are assigned to represent the “true” and “false” of the compare operation. If b and c are equal, p1 is true and p2 is false. If b and c are not equal p1 is false and p2 is true. These values of p1 and p2 are known as predicate guards.
The branched control flow graph can now be constructed as a straight line sequence of codes (block 50). Therefore, if p1 is true, a2=y and if p2 is true, a1=x. In this example, a3=Φ(a1, a2). This Φ is not occurring at a confluence at a joint point in the graph, but just in a straight line stream of instructions. Therefore, a3 equals either a1 or a2, depending on the value of these predicates. If z=a2 at some later point in the code, the value of a2 must be retained. However, if all of the variables are assigned to the same register, the value of a2 cannot be retained by materialization.
During code transformations, such interferences may be introduced between the Φ target and its sources. These interferences cannot be resolved simply by placing copy instructions on the incoming edges at the join point such as the example of setting t=a2 40 in FIG. 2b. This is because the copy instructions would effectively be on all paths.
A variable is live when it has been defined and its last use has not yet been reached. Because the variable's value is defined and is to be consumed at a later point in the instruction stream, its value must be preserved. In FIG. 3, there are multiple variables related by a single Φ and which are live concurrently. After predicated execution has been performed, the line of code z=a2 is moved below the point of the assignment to a3 at instruction 52.
The variable a3 is live at instruction 52 because, presumably, at some point the value of a3 is to be consumed. However, when p1 is “true,” the variable a2 is assigned the value y. Therefore, a2 is also live and both of these live values interfere because multiple live participants in a Φ cannot be assigned to the same register or variable location.
The original SSA formulation, described in Cytron, R., Ferrante, J., Rosen, B., Wegman, M., and Zadeck, K., “Efficiently Computing Static Single Assignment Form and Control Dependence Graph,” ACM Transactions on Programming Languages and Systems, 13(4):452490, October, 1991; and Choi, J., Cytron, R., Ferrante, J., “System and Method for Solving Monotone Information Propagation Problems,” U.S. Pat. No. 5,327,561 (July 1994), awarded to International Business Machines Corporation of Armonk, N.Y., did not address problems arising from the use of predicated execution.
A gated form of SSA, Gated Single Assignment (GSA) was proposed in Ballance, R., Maccabe, A., and Ottenstein, K., “The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages,” Proceedings of the SIGPLAN '90 Conference on Programming Language Design and Implementation, pp. 257-271, June 1990. The GSA approach is directed to interpreting, rather than translating a program from the source language to a machine language. Interpreting refers to performing the translation on the fly as the program is executed. An interpreter looks at a statement in a source language and directly executes it. An interpreter is essentially a phase of a virtual machine that implements the language in which the source programmer code is written. This is significantly different from translating a program from source language to machine language, and then executing the program.
In GSA, control dependence information is associated with each reaching definition at a Φ function (termed g functions in this formulation). One difference between GSA and SSA is the introduction of gates, which are conditions that guard the operands to Φ. A guard indicates when the operand would be selected.
However, this formulation again relies upon the association of the Φ node with the join point in the control flow graph, and expresses the full control dependence of each incoming edge at the join point, to wit, the entire chain of control decisions that would have had to be made for that path to have been selected. Thus, GSA does not address the problems of Φ materialization or predicated code. Finally, the Ballance, et al. formulation is limited to the evaluation of a single condition to select between only two possible values, and therefore does not handle the confluence of more than two paths.
It would therefore be an advantage to provide a method and apparatus that permits SSA-based transformation techniques to be applied to predicated code. It would be a further advantage if such method and apparatus permitted the use of more than two operands for a key function and addressed the problem of materialization and did not require a Φ function to be at a join point in a control flow graph.